////////////////////////////////////////////////////
// LinkList
////////////////////////////////////////////////////
#ifndef DDMCMC_LINKLIST
#define DDMCMC_LINKLIST

#include <memory.h>
#include <stdlib.h>
#include <math.h>
#include <new.h>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>

#include <opencv2/core/core.hpp>

#include "Matrix.h"
#include "vector.h"

class MCMC_Point
{
public:
	int x, y;

	bool operator==(const MCMC_Point &pt)
	{
		if (pt.x == x && pt.y == y)
			return true;
		else
			return false;
	}
	bool operator!=(const MCMC_Point &pt)
	{
		if (pt.x == x && pt.y == y)
			return false;
		else
			return true;
	}
	MCMC_Point& operator=(const MCMC_Point &pt)
	{
		x = pt.x;
		y = pt.y;
		return *this;
	}
};

template <class Tp>
class ListNode
{
public:
	ListNode<Tp>	*next;
	ListNode<Tp>	*prev;
	Tp				data;

public:
	// construction & destruction
	ListNode(){ next = NULL; prev = NULL; };
	~ListNode(){ next = NULL; prev = NULL; };

	// operators
	ListNode& operator=(const ListNode<Tp> &x);

	// operations
	Tp		Get(void);
	void	Set(const Tp &x);
};

template <class Tp>
ListNode<Tp>& ListNode<Tp>::operator=(const ListNode<Tp> &x)
{
	data = x.Get();
}

template <class Tp>
Tp ListNode<Tp>::Get(void)
{
	return data;
}

template <class Tp>
void ListNode<Tp>::Set(const Tp &x)
{
	data = x;
}

////////////////////////////////////////////////////
////////////////////////////////////////////////////
template <class Tp>
class LinkList
{
public:
	// construction & destruction
	LinkList();
	LinkList(LinkList<Tp> &a);
	~LinkList();
	void Empty(void);

	// operators
	LinkList<Tp>& operator=(LinkList<Tp> &x);
	LinkList<Tp> operator+(LinkList<Tp> &a1);
	/*friend ofstream & operator>>(LinkList<Tp> &x, ofstream &strm);
	friend ifstream & operator<<(LinkList<Tp> &x, ifstream &strm);*/

	void operator>>(ofstream &strm);
	void operator<<(ifstream &strm);

	// operations
	void	Insert(const Tp &x);
	void	InsertToHead(const Tp &x);
	void	Insert_unique(const Tp &x);
	bool	Delete(const Tp &x);
	bool	DeleteTheLast(void);
	bool	DeleteTheFirst(void);
	bool	GetFirst(Tp &x);
	bool	GetLast(Tp &x);
	Tp*		GetFirstPos(void);
	bool	GetCurrent(Tp &x);
	Tp*		GetCurrentPos(void);
	bool	GetNext(Tp &x);
	bool	GetPrev(Tp &x);
	Tp*		GetNextPos(void);
	Tp*		GetPos(const Tp &x);
	bool	IsIn(const Tp &x);
	void	Pop(void);
	inline	int Num(void) const { return count; };
	bool	IsAtTail(void){ if (move == tail) return true; else return false; };
	bool	InsertInfront(Tp &x, Tp &y);	// insert x in front of y
	bool	InsertBehind(Tp &x, Tp &y);		// insert x behind y
	bool	PopOut(Tp &x);
	void	ToMatrix(mcmcMatrix<Tp> &mx);
	void	ToVector(mcmcVector<Tp> &a) const;
	void	ToSimpleMatrix(SimpleMatrix<Tp> &a) const;

protected:
	ListNode<Tp>*	Find(const Tp &x);

private:
	ListNode<Tp>	*head, *move, *tail;
	int				count;
};

template <class Tp>
LinkList<Tp>::LinkList()
{
	head = NULL;
	move = NULL;
	tail = NULL;
	count = 0;
}

template <class Tp>
LinkList<Tp>::LinkList(LinkList<Tp> &a)
{
	head = NULL;
	move = NULL;
	tail = NULL;
	count = 0;

	(*this) = a;
}

template <class Tp>
LinkList<Tp>::~LinkList()
{
	Empty();
}


template <class Tp>
LinkList<Tp>& LinkList<Tp>::operator=(LinkList<Tp> &x)
{
	if (this != &x)
	{
		Empty();

		Tp		y;
		bool	bGo;
		bGo = x.GetFirst(y);
		while (bGo)
		{
			Insert(y);
			bGo = x.GetNext(y);
		}
	}
	return *this;
}

//template <class Tp>
//ofstream & operator>>(LinkList<Tp> &x, ofstream &strm)
//{
//	strm.write((char*)&(x.count), sizeof(x.count));
//
//	Tp		temp;
//	bool	bgo;
//
//	bgo = x.GetFirst(temp);
//	while (bgo)
//	{
//		strm.write((char*)&(temp), sizeof(temp));
//
//		bgo = x.GetNext(temp);
//	}
//
//	return strm;
//
//	
//}

template <class Tp>
void LinkList<Tp>::operator>>(ofstream &strm)
{
	strm.write((char*)&(count), sizeof(count));

	Tp		temp;
	bool	bgo;

	bgo = GetFirst(temp);
	while (bgo)
	{
		strm.write((char*)&(temp), sizeof(temp));

		bgo = GetNext(temp);
	}
}

//template <class Tp>
//ifstream & operator<<(LinkList<Tp> &x, ifstream &strm)
//{
//	x.Empty();
//
//	int num;
//	Tp	temp;
//
//	strm.read((char*)&(num), sizeof(num));
//
//	for (int i=0; i<num; i++)
//	{
//		strm.read((char*)&(temp), sizeof(temp));
//		x.Insert(temp);
//	}
//
//	return strm;
//	
//}
template <class Tp>
void LinkList<Tp>::operator<<(ifstream &strm)
{
	Empty();

	int num;
	Tp	temp;

	strm.read((char*)&(num), sizeof(num));

	for (int i = 0; i<num; i++)
	{
		strm.read((char*)&(temp), sizeof(temp));
		Insert(temp);
	}
}


template <class Tp>
void LinkList<Tp>::Empty(void)
{
	while (head != NULL)
	{
		move = head;
		head = head->next;
		delete move;
	}
	head = NULL;
	move = NULL;
	tail = NULL;
	count = 0;
}

template <class Tp>
bool LinkList<Tp>::GetFirst(Tp &x)
{
	move = head;
	if (move == NULL)
		return false;
	else
	{
		x = move->Get();
		return true;
	}
}

template <class Tp>
bool LinkList<Tp>::GetLast(Tp &x)
{
	move = tail;
	if (move == NULL)
		return false;
	else
	{
		x = move->Get();
		return true;
	}
}

template <class Tp>
Tp*	LinkList<Tp>::GetFirstPos(void)
{
	Tp x;

	GetFirst(x);
	if (move != NULL)
		return &(move->data);
	else
		return NULL;
}

template <class Tp>
Tp*	LinkList<Tp>::GetCurrentPos(void)
{
	if (move != NULL)
		return &(move->data);
	else
		return NULL;
}

template <class Tp>
bool LinkList<Tp>::GetCurrent(Tp &x)
{
	if (move != NULL)
	{
		x = move->data;
		return true;
	}
	else
		return false;
}

template <class Tp>
bool LinkList<Tp>::GetNext(Tp &x)
{
	if (move == NULL)
		return false;
	else
	{
		move = move->next;
		if (move == NULL)
			return false;
		else
		{
			x = move->Get();
			return true;
		}
	}
}

template <class Tp>
bool LinkList<Tp>::GetPrev(Tp &x)
{
	if (move == NULL)
		return false;
	else
	{
		move = move->prev;
		if (move == NULL)
			return false;
		else
		{
			x = move->Get();
			return true;
		}
	}
}

template <class Tp>
Tp*	LinkList<Tp>::GetNextPos(void)
{
	Tp x;

	GetNext(x);
	if (move != NULL)
		return &(move->data);
	else
		return NULL;
}

template <class Tp>
void LinkList<Tp>::Insert(const Tp &x)
{
	ListNode<Tp> *newNode;

	newNode = new ListNode<Tp>;
	if (newNode == NULL)
		exit(0);

	newNode->Set(x);
	if (head == NULL)
	{
		// empty link list
		head = newNode;
		tail = head;
	}
	else
	{
		tail->next = newNode;
		newNode->prev = tail;
		tail = newNode;
	}
	count++;
}

template <class Tp>
void LinkList<Tp>::InsertToHead(const Tp &x)
{
	ListNode<Tp> *newNode;

	newNode = new ListNode<Tp>;
	if (newNode == NULL)
		exit(0);

	newNode->Set(x);
	if (head == NULL)
	{
		// empty link list
		head = newNode;
		tail = head;
	}
	else
	{
		head->prev = newNode;
		newNode->next = head;
		head = newNode;
	}
	count++;
}

// insert x in front of y
template <class Tp>
bool LinkList<Tp>::InsertInfront(Tp &x, Tp &y)
{
	ListNode<Tp> *newNode, *py;

	py = Find(y);
	if (py == NULL)
		return false;

	newNode = new ListNode<Tp>;
	if (newNode == NULL)
		exit(0);
	newNode->Set(x);
	if (py->prev != NULL)
	{
		py->prev->next = newNode;
		newNode->prev = py->prev;
	}

	py->prev = newNode;
	newNode->next = py;

	if (head == py)
		head = newNode;

	count++;
	return true;
}

// insert x behind y
template <class Tp>
bool LinkList<Tp>::InsertBehind(Tp &x, Tp &y)
{
	ListNode<Tp> *newNode, *py;

	py = Find(y);
	if (py == NULL)
		return false;

	newNode = new ListNode<Tp>;
	if (newNode == NULL)
		exit(0);
	newNode->Set(x);
	if (py->next != NULL)
	{
		py->next->prev = newNode;
		newNode->next = py->next;
	}

	py->next = newNode;
	newNode->prev = py;
	if (tail == py)
		tail = newNode;

	count++;
	return true;
}


template <class Tp>
void LinkList<Tp>::Pop(void)
{
	if (head != NULL)
	{
		if (tail == head)
		{
			tail = NULL;
			delete head;
			head = NULL;
		}
		else
		{
			ListNode<Tp> *temp;
			temp = head;
			head = head->next;
			if (head != NULL)
				head->prev = NULL;
			delete temp;
		}
		count--;
	}
}

template <class Tp>
bool LinkList<Tp>::Delete(const Tp &x)
{
	Tp			 y;
	ListNode<Tp> *temp;

	move = head;
	while (move != NULL)
	{
		y = move->Get();
		if (y == x && move == head)
		{
			head = move->next;
			if (tail == move)
				tail = head;
			count--;
			delete move;
			if (head != NULL)
				head->prev = NULL;

			return true;
		}
		else
		{
			if (move->next != NULL)
			{
				y = move->next->Get();
				if (y == x)
				{
					temp = move->next;
					move->next = move->next->next;
					if (move->next != NULL)
						move->next->prev = move;
					if (tail == temp)
						tail = move;
					count--;
					delete temp;
					return true;
				}
			}
		}
		move = move->next;
	}
	return false;
}

template <class Tp>
bool LinkList<Tp>::DeleteTheLast(void)
{
	if (tail == NULL)
		return false;

	if (head == tail)
	{
		delete head;

		count--;
		head = NULL;
		tail = NULL;

		return true;
	}
	else
	{
		ListNode<Tp> *temp;

		temp = tail;

		tail = tail->prev;
		tail->next = NULL;

		count--;
		delete temp;
		return true;
	}
}

template <class Tp>
bool LinkList<Tp>::DeleteTheFirst(void)
{
	if (head == NULL)
		return false;

	if (head == tail)
	{
		delete head;

		count--;
		head = NULL;
		tail = NULL;

		return true;
	}
	else
	{
		ListNode<Tp> *temp;

		temp = head;

		head = head->next;
		head->prev = NULL;

		count--;
		delete temp;
		return true;
	}
}


template <class Tp>
bool LinkList<Tp>::IsIn(const Tp &x)
{
	bool bGo;
	Tp	 y;

	bGo = GetFirst(y);
	while (bGo)
	{
		if (y == x)
			return true;
		bGo = GetNext(y);
	}

	return false;
}

template <class Tp>
ListNode<Tp>* LinkList<Tp>::Find(const Tp &x)
{
	bool bGo;
	Tp	 y;

	bGo = GetFirst(y);
	while (bGo)
	{
		if (y == x)
			return move;
		bGo = GetNext(y);
	}

	return NULL;
}

template <class Tp>
void LinkList<Tp>::Insert_unique(const Tp &x)
{
	if (!IsIn(x))
		Insert(x);
}


template <class Tp>
Tp*	LinkList<Tp>::GetPos(const Tp &x)
{
	bool bGo;
	Tp	 y;

	bGo = GetFirst(y);
	while (bGo)
	{
		if (y == x)
			return &(move->data);
		bGo = GetNext(y);
	}
	return NULL;
}

template <class Tp>
void LinkList<Tp>::ToMatrix(mcmcMatrix<Tp> &mx)
{
	bool	bGo;
	Tp		x;
	int		i;

	mx.SetDimension(Num(), 1);
	i = 0;
	bGo = GetFirst(x);
	while (bGo)
	{
		mx(i++) = x;
		bGo = GetNext(x);
	}

}

template <class Tp>
bool LinkList<Tp>::PopOut(Tp &x)
{
	bool bgo = GetFirst(x);
	Pop();
	return bgo;
}


template <class Tp>
void LinkList<Tp>::ToVector(mcmcVector<Tp> &a) const
{
	int			 i;
	ListNode<Tp> *pmove_temp;

	// intialization
	a.SetRowVector(Num());
	i = 0;

	pmove_temp = head;

	while (pmove_temp != NULL)
	{
		a(i++) = pmove_temp->Get();

		pmove_temp = pmove_temp->next;
	}
}

template <class Tp>
void LinkList<Tp>::ToSimpleMatrix(SimpleMatrix<Tp> &a) const
{
	int			 i;
	ListNode<Tp> *pmove_temp;

	// intialization
	a.SetDimension(1, Num());
	i = 0;

	pmove_temp = head;

	while (pmove_temp != NULL)
	{
		a(i++) = pmove_temp->Get();

		pmove_temp = pmove_temp->next;
	}
}


template <class Tp>
LinkList<Tp> LinkList<Tp>::operator+(LinkList<Tp> &a2)
{
	LinkList<Tp>	b;
	Tp				x;
	bool			bgo;

	// the first list
	bgo = GetFirst(x);
	while (bgo)
	{
		b.Insert(x);
		bgo = GetNext(x);
	}
	// the second list
	bgo = a2.GetFirst(x);
	while (bgo)
	{
		b.Insert(x);
		bgo = a2.GetNext(x);
	}
	return b;
}





#endif
